package leetcode.templates.maths.random;

//执行用时：49 ms, 在所有 Java 提交中击败了99.90%的用户
//
//内存消耗：49.3 MB, 在所有 Java 提交中击败了42.74%的用户
//
//通过测试用例：14 / 14
// 水塘抽样
public class Solution {

	int[] nums;

	public Solution(int[] nums) {
		this.nums = nums;
	}

	public int pick(int target) {
		int ans = 0;
		int cnt = 1;
		for (int i = 0; i < nums.length; i++) {
			if (target == nums[i]) {
				if ((int) (Math.random() * cnt) == 0) {
					ans = i;
				}
				cnt++;
			}
		}
		return ans;
	}

}
